package cg.studio.practise;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

import org.junit.Test;

/**
 * Given a number such as 123 having digits 1,2 and 3. 
   Now Product of Number and its digits is = 123*1*2*3 = 768. 
   Now 123 is the seed number for 768. 
   You would be given a number and you have to identify whether any seed element exists for that number. 
   for Ex: - 4977 has two such seed numbers 79 and 711. You have to print both.
 * 
 * solution: for a give number(num)
 *   - calculate factors less than 10 ( digit )
 *   - combine this digits( can be duplicated ) until otherFactor > min( number formed by digits, and check
 *     - otherFactor = num/digits
 *     - otherFactor can't be represents by digits( otherFactor must not less than the small number formed by digits )
 *     
 * for example: num = 4977 = 711*7*1*1 = 79*7*9
 *   - digit factors are: 1, 3, 7, 9
 *   - determine the max digits could be, as 11111 > 4977, so max 4 digit ( maxDigitCount )
 *   - for ( digitCount : maxDigitCount )
 *     - digitCount == 1: impossible
 *     - digitCount == 2: check( 1, 1 ), (1,3)...(1,9)......(9,9), found 79
 *     - ....   
 * @author Bright Chen
 *
 */
public class ProductSeeds
{
  @Test
  public void testGetSeeds()
  {
    int[] numbers = new int[]{ 738, 4977 };
    for( int number : numbers )
    {
      int[] seeds = getSeeds( number );
      if( seeds != null )
      {
        System.out.print( "seeds for number " + number + ": "  );
        for( int seed : seeds )
        {
          System.out.print( seed + ", " );
        }
        System.out.println();
      }
    }
  }
  
  public static int[] getSeeds( int num )
  {
    Set<Integer> seeds = new HashSet<Integer>();

    //calculate the digit factors
    int[] digits = new int[9];
    digits[0] = 1;
    int digitCount = 1;
    for( int i=2; i<10; ++i )
    {
      if( num % i == 0 )
        digits[ digitCount++ ] = i;
    }
    digits = Arrays.copyOfRange( digits, 0, digitCount );
    
    //calculate the largest digit count, basically compare num with 111...1
    int maxDigitCount = 1;
    int value = 1;
    for( ; value < num; ++maxDigitCount )
    {
      value = value*10 + 1;
    }
    if( value == num )
      seeds.add( value );
    --maxDigitCount;
    
    for( int digitNum = 1; digitNum <= maxDigitCount; ++digitNum )
    {
      int[] selectedDigits = new int[ digitNum ];
      getSeeds( num, selectedDigits, 0, digits, digitNum, seeds );
    }
    
    if( seeds.isEmpty() )
      return null;
    int[] iSeeds = new int[ seeds.size() ];
    int i=0;
    for( Integer seed : seeds )
    {
      iSeeds[i++] = seed;
    }
    return iSeeds;
  }
  
  
  /**
   * 
   * @param num
   * @param combined the digits used to combine the number
   * @param digits 
   * @param seeds the generated the seeds, this is output
   */
  /**
   * 
   * @param num
   * @param digitPool the digit pool we can select to generate
   * @param digitNum number of digit used to generate products and seeds
   * @param seeds
   */
  /**
   * 
   * @param num
   * @param selectedDigits the digits already selected by previous recursive
   * @param selectedDigitCount how many digits already selected
   * @param digitPool the pool of the digit for selection
   * @param digitNum the number of digits we should select before verify.
   * @param seeds
   */
  public static void getSeeds( final int num, int[] selectedDigits, int selectedDigitCount, int[] digitPool, 
                               int digitNum, Set<Integer> seeds )
  {
    if( selectedDigitCount == digitNum )
    {
      //all the digits selected, calculate and check
      int candidateSeed = getNumberOfSortedDigits( selectedDigits );
      int products = candidateSeed;
      for( int i=0; i<selectedDigitCount; ++i )
      {
        products *= selectedDigits[i];
      }
      if( products == num )
      {
        //this is seed
        seeds.add( candidateSeed );
      }
      return;
    }
    
    for( int poolIndex=0; poolIndex<digitPool.length; ++poolIndex )
    {
      selectedDigits[ selectedDigitCount ] = digitPool[ poolIndex ];
      getSeeds( num, selectedDigits, selectedDigitCount+1, digitPool, digitNum, seeds );
    }

  }
  
  public static int getNumberOfSortedDigits( int[] digits )
  {
    int num = 0;
    for( int digit : digits )
    {
      num = num*10 + digit;
    }
    return num;
  }
}
